# LeetCode 409、最长回文串

# 一、题目描述

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
输入:1

示例 3:

输入:s = "bb"
输入: 2

提示:

1 <= s.length <= 2000
s 只能由小写和/或大写英文字母组成

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长回文串（LeetCode 409）：https://leetcode.cn/problems/longest-palindrome/
class Solution {
    public int longestPalindrome(String s) {

        // 手动设置哈希表，哈希函数为 c - 'A'
        // 这里的哈希表的作用是计数器
        // 由于 大写字母 'A' 与小写字母 'a' 的 ASCII 相差 32
        // A : 65
        // a : 97
        // 所以设置哈希表的大小为 32 + 26 = 58
        int[] cnt = new int[58];

        // 统计每个字母出现的频次
        for (char c : s.toCharArray()) {

            cnt[c - 'A'] += 1;
        }

        // 初始化结果
        int ans = 0;

        for (int x: cnt) {

            // 根据奇偶性来判断当前字母的使用次数为多少   
            // 按位与：& 
            // 将参与运算的两操作数各对应的二进制位进行与操作
            // 只有对应的两个二进位均为 1 时，结果的对应二进制位才为 1 ，否则为 0
            // 通过这个方法判断 x 的奇偶性，即统计这个字母出现的是偶数次还是奇数次
            // 1 的二进制为          0001 
            // 比如 x 为 4，二进制为  0100 ，那么 x & 1 的结果是 0000 ，即为 0
            // 那么 x -  (x & 1) 的结果是 4，那么这 4 个字母全部都可以出现在最终的回文串中
            // **********
            // 比如 x 为 5，二进制为  0101 ，那么 x & 1 的结果是 0001 ，即为 1
            // 那么 x -  (x & 1) 的结果是 4，即出现了 5 次的那个字母只有其中 4 个可以被用上
            ans += x - (x & 1);

        }

        // 最后，会尝试一下，能不能再添加一个字符到回文串中
        // 如果最终的长度小于原字符串的长度，说明里面某个字符出现了奇数次，那么那个字符可以放在回文串的中间，所以额外再加一
        return ans < s.length() ? ans + 1 : ans;  
    }
}

# 2、C++ 代码

class Solution {
public:
    int longestPalindrome(string s) {

        // 手动设置哈希表，哈希函数为 c - 'A'
        // 这里的哈希表的作用是计数器
        // 由于 大写字母 'A' 与小写字母 'a' 的 ASCII 相差 32
        // A : 65
        // a : 97
        // 所以设置哈希表的大小为 32 + 26 = 58
        int cnt[58] = {0};

        // 统计每个字母出现的频次
        for(string::size_type i = 0; i < s.size(); i++) {
            if('a' <= s[i] && s[i] <= 'z') {
                cnt[s[i]-'a']++;
            } else {
                cnt[s[i]-'A'+26]++;
            }
        }

        // 初始化结果
        int ans = 0;

        for (int x: cnt) {

            // 根据奇偶性来判断当前字母的使用次数为多少   
            // 按位与：& 
            // 将参与运算的两操作数各对应的二进制位进行与操作
            // 只有对应的两个二进位均为 1 时，结果的对应二进制位才为 1 ，否则为 0
            // 通过这个方法判断 x 的奇偶性，即统计这个字母出现的是偶数次还是奇数次
            // 1 的二进制为          0001 
            // 比如 x 为 4，二进制为  0100 ，那么 x & 1 的结果是 0000 ，即为 0
            // 那么 x -  (x & 1) 的结果是 4，那么这 4 个字母全部都可以出现在最终的回文串中
            // **********
            // 比如 x 为 5，二进制为  0101 ，那么 x & 1 的结果是 0001 ，即为 1
            // 那么 x -  (x & 1) 的结果是 4，即出现了 5 次的那个字母只有其中 4 个可以被用上
            ans += x - (x & 1);

        }

        // 最后，会尝试一下，能不能再添加一个字符到回文串中
        // 如果最终的长度小于原字符串的长度，说明里面某个字符出现了奇数次，那么那个字符可以放在回文串的中间，所以额外再加一
        return ans < s.length() ? ans + 1 : ans; 

    }
};

# 3、Python 代码

class Solution:
    def longestPalindrome(self, s: str) -> int:

        # 手动设置哈希表，哈希函数为 c - 'A'
        # 这里的哈希表的作用是计数器
        # 由于 大写字母 'A' 与小写字母 'a' 的 ASCII 相差 32
        # A : 65
        # a : 97
        # 所以设置哈希表的大小为 32 + 26 = 58
        l_s = list(s)
        #字典来存储每个字母出现的个数
        cnt = {}
        for word in l_s:
            cnt[word] = 0

        for word in l_s:
            cnt[word] += 1

        ans = 0

        for key, value in cnt.items():
            #如果出现个数为偶数，直接加入
            if value % 2 == 0:
                ans += value
            else:
                #如果为奇数，则加value - 1，并且，该字母的次数变为1
                ans += value - 1
                cnt[key] = 1 
       
        return  ans + 1 if 1 in cnt.values() else ans

← LeetCode 205、同构字符串 LeetCode 387、字符串中的第一个唯一字符 →

# LeetCode 409、最长回文串

# 一、题目描述

# 二、题目解析

# 三、参考代码

# 1、Java 代码

# **2、**C++ 代码

# 3、Python 代码

# 2、C++ 代码